package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/7/29 23:11
 */
public class Flatten_114 {

    public void flatten(TreeNode root) {
        if (root == null) return;
        // 注意修改的顺序
        flatten(root.left);
        flatten(root.right);
        // 先备份右子树
        TreeNode right = root.right;
        // 将左子树换到右边
        root.right = root.left;
        // 左子树置空
        root.left = null;
        // 这里有一次链表的遍历
        // 左子树可能很长，需要遍历到最底层再进行添加
        while (root.right != null) root = root.right;
        // 将右子树添加到末尾
        root.right = right;
    }

    TreeNode before;

    public void flatten2(TreeNode root) {
        if (root == null) return;
        // 将结点通过右子树连接
        flatten(root.right);
        flatten(root.left);
        // 将之前已经连接好的节点加到右子树中
        root.right = before;
        // 所以左子树可以直接置为NULL
        root.left = null;
        // root就已经包括上一次遍历的左孩子
        before = root;
    }

    static class Solution {
        public void flatten(TreeNode root) {
            if (root == null) return;
            flatten(root.left);
            flatten(root.right);
            TreeNode right = root.right;
            root.right = root.left;
            root.left = null;
            while (root.right != null) root = root.right;
            root.right = right;
        }
    }


}
